//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/?envType=daily-question&envId=2024-02-22https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/?envType=daily-question&envId=2024-02-22

class Solution {
public:
    TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder) {
        function<TreeNode *(int, int, int, int)> get = [&](int pl, int pr, int bl, int br) {
            if (pl > pr)
                return (TreeNode *) nullptr;
            TreeNode *res = new TreeNode(preorder[pl]);
            if (pl == pr)
                return res;
            unordered_set<int> v1, v2;//集合记录两个子数组中有哪些数
            int c1 = 0, c2 = 0;//c1:v1中不在v2中的元素数，c2:v2中不在v1中的元素数
            int i = pl + 1, j = bl;
            for (; i <= pr; i++, j++) {
                v1.insert(preorder[i]);
                v2.insert(postorder[j]);
                if (preorder[i] != postorder[j]) {
                    if (!v1.count(postorder[j]))
                        c2++;
                    else
                        c1--;
                    if (!v2.count(preorder[i]))
                        c1++;
                    else
                        c2--;
                }
                if (c1 == 0 && c2 == 0)
                    break;
            }
            res->left = get(pl + 1, i, bl, j);
            res->right = get(i + 1, pr, j + 1, br - 1);
            return res;
        };
        return get(0, preorder.size() - 1, 0, preorder.size() - 1);
    }
};


